/**
 * 
 * leecode 官方题解，暂不满足
 * @param {number[]} nums
 * @return {number[]}
 */
var lengthOfLIS = function (nums) {

    let len = 1
    let n = nums.length
    if (n === 0) {
        return
    }

    let rslt = []

    let d = new Array(n + 1).fill()
    d[len] = nums[0]
    for (let i = 1; i < n; i++) {
        if (nums[i] > d[len]) {
            d[++len] = nums[i]
            rslt.push(nums[i])
            // rslt = d.filter(val => typeof val !== 'undefined')
            console.log(rslt, d)
        } else {
            // 二分法找到第一个小于nums[i]的元素位置 k, d[k+1] = nums[i]
            let l = 1
            let r = len
            let pos = 0
            while (l <= r) {
                const mid = Math.floor((l + r) / 2)
                if (d[mid] < nums[i]) {
                    pos = mid
                    l = mid + 1
                } else {
                    r = mid - 1
                }
            }
            d[pos + 1] = nums[i]
        }
    }
    console.log(len, d)
    return rslt





}

// 2,3,7,8,10,13
lengthOfLIS([4, 3, 5, 0, 8, 4, 12, 2, 14])

4, 3, 5, 0, 8, 4, 12, 2, 14
4, 3, 5, 0, 8, 4, 12, 2, 14
4, 3, 5, 0, 8, 4, 12, 2, 14


